The cost of a path is defined as the sum of the weights of all edges traversed, allowing us to compare different routes.
- The cost of a path $P$ is the sum of the weights $w(u, v)$ of all edges it traverses.
- We seek the path $P$ from source $s$ to target $t$ that minimizes $Cost(P)$.
- Example Path 1: $P_1 = (A, B, D)$ has a cost of $w(A, B) + w(B, D) = 5 + 4 = 9$.
- Example Path 2: $P_2 = (A, C, D)$ has a cost of $w(A, C) + w(C, D) = 2 + 6 = 8$.
- Example Path 3: $P_3 = (A, B, C, D)$ has a cost of $5 + 1 + 6 = 12$.
- Comparing the paths, $P_2$ is the shortest path found so far with a cost of 8.
Formal Definition of Path Cost
$$
Cost(P) = \sum_{i=1}^{k-1} w(v_i, v_{i+1})
$$